package com.yulongtian.weekCompetition.month202212.week2;

import java.util.*;

/**
 * 可
 *
 * @author yulongTian
 * @create 2022-12-10 22:37
 */
public class Test02 {
    public static void main(String[] args) {
        int[] vals = {17, 49, -34, -17, -7, -23, 24};
        int[][] edges = {{3, 1}, {5, 1}, {0, 3}, {4, 6}, {1, 4}, {3, 4}, {6, 3}, {2, 6}, {5, 2}, {1, 6}, {6, 0}, {2, 3}, {3, 5}, {2, 1}, {0, 2}, {5, 0}, {0, 4}};
        System.out.println(maxStarSum(vals, edges, 2));
    }

    public static int maxStarSum(int[] vals, int[][] edges, int k) {
        if (vals.length == 1 && k == 0) {
            return vals[0];
        }
        //邻接表
        HashMap<Integer, List<Integer>> gridList = gridList(vals, edges);

        Set<Integer> integers = gridList.keySet();
        int res = Integer.MIN_VALUE;
        for (Integer integer : integers) {
            List<Integer> nexts = gridList.get(integer);
            int temp = vals[integer];
            res = Math.max(res, temp);


            nexts.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });

            for (int i = 0; i < Math.min(k, nexts.size()); i++) {
                temp += nexts.get(i);
                res = Math.max(res, temp);
            }
        }
        return res;
    }


    public static HashMap<Integer, List<Integer>> gridList(int[] vals, int[][] edges) {
        HashMap<Integer, List<Integer>> res = new HashMap<>();

        for (int i = 0; i < vals.length; i++) {
            res.put(i, new ArrayList<>());
        }

        for (int[] edge : edges) {
            res.get(edge[0]).add(vals[edge[1]]);
            res.get(edge[1]).add(vals[edge[0]]);
        }
        return res;
    }


}
